//class Solution {
//    public int numDecodings(String s) {
//        // 1、创建 dp 表
//        // 2、初始化
//        // 3、填充dp表
//        // 4、返回值
//
//        int n = s.length();
//        char[] str = s.toCharArray();
//        int[] dp = new int[n];
//        // 判断第1个位置是否能单独解码
//        if (str[0] != '0') { // ['1', '9']可以单独解码
//            dp[0] = 1;
//        }
//        // 排除只有1个字符的情况
//        if (n == 1) {
//            return dp[0];
//        }
//        // 判断第二个位置是否可以单独解码，以及配合解码
//        if (str[1] != '0' && str[0] != '0') { // 单独解码(第一个位置也要可以)
//            dp[1] += 1;
//        }
//        // 配合解码就是指两者相加之和处于[10, 26]之间
//        // 前导0是不能解码的
//        int t = (str[0]-'0') * 10 + str[1] - '0';
//        if (t >= 10 && t <= 26) {
//            dp[1] += 1;
//        }
//
//        for (int i = 2; i < n; i++) {
//            // 判断 i 位置是否可以单独解码以及配合解码
//            if (str[i] != '0') {
//                dp[i] += dp[i-1];
//            }
//            t = (str[i-1] - '0') * 10 + str[i] - '0';
//            if (t >= 10 && t <= 26) {
//                dp[i] += dp[i-2];
//            }
//        }
//        // 返回n-1为结尾时，解码的总数
//        return dp[n-1];
//    }
//}


class Solution {
    public int numDecodings(String s) {
        int n = s.length();
        char[] str = s.toCharArray();
        int[] dp = new int[n+1];
        dp[0] = 1; // 一定要初始化为1
        // 判断第1个位置是否能单独解码
        if (str[0] != '0') { // ['1', '9']可以单独解码
            dp[1] = 1;
        }
        // 排除只有1个字符的情况
        if (n == 1) {
            return dp[1];
        }

        for (int i = 2; i <= n; i++) {
            // 判断 i 位置是否可以单独解码以及配合解码
            if (str[i-1] != '0') {
                dp[i] += dp[i-1];
            }
            int t = (str[i-2] - '0') * 10 + str[i-1] - '0';
            if (t >= 10 && t <= 26) {
                dp[i] += dp[i-2];
            }
        }
        // 返回n-1为结尾时，解码的总数
        return dp[n];
    }
}